class Walk {
  int N;                                                      // number of steps (number of points is N+1)
  int DIM;                                                    // dimensionality
  int R_EE;                                                   // squered end to end distance
  int * steps;
  int * positions;                                            
public:
  int get_step(int step_num);                                 // returns step number step_num (from 0 to N-1)
  void get_pos(int pos_num,int * pos);                        // return the position of point point_num (0-N)
  int get_length();                                           // returns number of steps
  void set_R_EE();                                            // calculates R_EE
  int get_R_EE();                                             // returns R_EE
  void make_random();                                         // creates a random walk - requires RNG!!
  bool check_SA(Table&);                                      // check SA
  void read_steps(int * in_steps);                            // builds a walk matching a series of steps given in the array in_steps
  void set_step(int step_num, int step);                      // sets step number step_num to step
  void set_start(int[]);                                      // sets starting position
  void set_pos(int point_num,int point_pos[]);                // sets position of point number point_num to be point_pos
  void detailed_print();                                      // detailed print of the walk (on screen)
  void print_steps(ofstream & output);                        // prints the steps into a file
  void print_pos(int pos_num);                                // prints position of piont number point_num
  void add_walks(Walk& walk1,Walk& walk2);                    // adds a second walk at the end of the first
  void split_walk(Walk& walk1,Walk& walk2);                   // splits walk into two smaller walks
  void kantor_fun(int *);                                     // calculates kantors function
  Walk(int n,int d);                                          // initializes a walk of n steps in a d dimensional space
  ~Walk();                                                    // clears dynamic memory
};


void Walk::read_steps(int * in_steps) {
  int i;
  int * pos;
  pos = new int[DIM];
  get_pos(0,pos);
  for (i=0;i<N;i++) {
    steps[i]=in_steps[i];
    switch(in_steps[i]) {
    case 1:
      pos[0]++;
	break;
    case 2:
      pos[0]--;
      break;
    case 3:
      pos[1]++;
      break;
    case 4:
      pos[1]--;
      break;
    case 5:
      pos[2]++;
      break;
    case 6:
      pos[2]--;
      break;
    }
    set_pos(i+1,pos);
    //cout << "in_step: " << in_steps[i] << ", steps: " << steps[i] << "\n";
    //cout << "pos: " << pos[0] << "," << pos[1] << "," << pos[2] << "\n";
  }
  set_R_EE();
  delete [] pos;
}


int Walk::get_length() {
  return N;
    }

void Walk::set_R_EE() {
  int i;
  int * start;
  int * end;
  start = new int[DIM];
  end = new int[DIM];
  get_pos(0,start);
  get_pos(N,end);
  R_EE=0;
  for (i=0;i<DIM;i++) {
    R_EE=R_EE+(start[i]-end[i])*(start[i]-end[i]);
  }
  delete [] start;
  delete [] end;
}

Walk::Walk(int n, int d) {
  int i,j;
  N=n;
  DIM=d;
  R_EE=0;
  steps = new int[N];
  positions = new int[(N+1)*d];
  for (i=0;i<N;i++) {
    steps[i]=0;
    for (j=0;j<d;j++) {
      positions[i*d+j]=0;
    }
  }
  for (i=0;i<d;i++) {
    positions[N*d+i]=0;
  }
}

int Walk::get_R_EE() {
  return R_EE;
}

Walk::~Walk() {
  //cout << "class destroid\n";
  delete [] steps;
  delete [] positions;
}



void Walk::add_walks (Walk& walk1,Walk& walk2) {
  int i,N2,N1,j;
  int * pos;
  int * end_pos1;
  int * st_pos2;
  pos = new int[DIM];
  end_pos1 = new int[DIM];
  st_pos2 = new int[DIM];
  N1=walk1.get_length();
  N2=walk2.get_length();
  walk1.get_pos(N1,end_pos1);
  walk2.get_pos(0,st_pos2);
  for (i=0;i<N1;i++) {
    set_step(i,walk1.get_step(i));
    walk1.get_pos(i,pos);
    set_pos(i,pos);
  }
  for (i=N1;i<N1+N2;i++) {
    set_step(i,walk2.get_step(i-N1));
    walk2.get_pos(i-N1,pos);
    for (j=0;j<DIM;j++) {
      pos[j]=pos[j]+end_pos1[j]-st_pos2[j];
    }
    set_pos(i,pos);
  }
  walk2.get_pos(N2,pos);
  for (j=0;j<DIM;j++) {
      pos[j]=pos[j]+end_pos1[j]-st_pos2[j];
  }
  set_pos(N1+N2,pos);
  set_R_EE();
  delete [] pos;
  delete [] end_pos1;
  delete [] st_pos2;
 }

void Walk::split_walk(Walk& walk1,Walk& walk2) {
  int i,n1,n2;
  int * pos;
  n1=walk1.get_length();
  n2=walk2.get_length();
  pos=new int[DIM];
  for (i=0;i<n1;i++) {
    get_pos(i,pos);
    walk1.set_pos(i,pos);
    walk1.set_step(i,get_step(i));
  }
  get_pos(n1,pos);
  walk1.set_pos(n1,pos);
  for (i=0;i<n2;i++) {
    get_pos(i+n1,pos);
    walk2.set_pos(i,pos);
    walk2.set_step(i,get_step(i+n1));
  }
  get_pos(n1+n2,pos);
  walk2.set_pos(n2,pos);
  delete [] pos;
  walk1.set_R_EE();
  walk2.set_R_EE();
}

int Walk::get_step(int step_num) {
  return steps[step_num];
}

void Walk::set_step(int step_num,int step) {
  steps[step_num]=step;
}

void Walk::set_pos(int point_num,int point_pos[]) {
  int i;
  for (i=0;i<DIM;i++) {
    positions[point_num*DIM+i]=point_pos[i];
  }
}

void Walk::set_start(int st[]) {
  int i,j;
  int * pos;
  int * diff;
  int check;
  pos = new int[DIM];
  diff = new int[DIM];
  get_pos(0,pos);
  set_pos(0,st);
  check=0;
  for (i=0;i<DIM;i++) {
    if (pos[i]!=st[i]) check=1;
  }
  if (check==1) {
    for (i=0;i<DIM;i++) {
      diff[i]=st[i]-pos[i];
    }
    for (i=0;i<N;i++) {
      get_pos(i+1,pos);
      for (j=0;j<DIM;j++) {
	pos[j]=pos[j]+diff[j];
      }
      set_pos(i+1,pos);
    }
    delete [] pos;
    delete [] diff;
  }
}

    
    
void  Walk::get_pos(int pos_num,int * pos) {
  int i;
  for (i=0;i<DIM;i++) {
    pos[i]= positions[pos_num*DIM+i];
  }
}


void Walk::print_steps(ofstream & output) {
 int i;

  for (i=0;i<N;i++) {
    output << steps[i];
  }
  //output << "\n";
}

void Walk::print_pos(int pos_num) {
  int i;
  int * pos;
  pos = new int[DIM];
  get_pos(pos_num,pos);
  for (i=0;i<DIM;i++) {
    cout << pos[i] << "\t";
  }
  cout << "\n";
  delete [] pos;
}
  

void Walk::detailed_print() {
  int i,j;
  int * pos;
  pos = new int[DIM];
  cout << "\n";
  for (i=0;i<N;i++) {
    cout << "position " << i << ": ";
    get_pos(i,pos);
    cout << pos[0];
    for (j=1;j<DIM;j++) {
      cout << ", " << pos[j];
    }
    cout << "\n";
    cout << "step: " << steps[i] << "\n";
  }
  get_pos(N,pos);
  cout << "position " << N << ": ";
  cout << pos[0];
  for (j=1;j<DIM;j++) {
    cout << ", " << pos[j];
  }
  cout << "\n";
  cout << "squered end to end distance: " << R_EE << "\n";
  delete [] pos;
}


void Walk::make_random() {
  int r;
  int s,i,j;
  int * start;
  int * end;
  start = new int[DIM];
  end = new int[DIM];
  for (i=0;i<N;i++) {
    s=ran2_int(&idum,1,DIM*2);
    steps[i]=s;
    for (j=0;j<DIM;j++) {
      positions[(i+1)*DIM+j]=positions[i*DIM+j];
    }
    switch(s) {
      case 1:
        positions[(i+1)*DIM]++;
	break;
      case 2:
	positions[(i+1)*DIM]--;
	break;
      case 3:
	positions[(i+1)*DIM+1]++;
	break;
      case 4:
	positions[(i+1)*DIM+1]--;
	break;
      case 5:
	positions[(i+1)*DIM+2]++;
	break;
      case 6:
	positions[(i+1)*DIM+2]--;
	break;
    }
  }
  get_pos(0,start);
  get_pos(N,start);
  for (i=0;i<DIM;i++) {
    R_EE=R_EE+(start[i]-end[i])*(start[i]-end[i]);
  }
  delete [] start;
  delete [] end;
}

bool Walk::check_SA(Table& table1) {
  int * pos1;
  int * pos2;
  int i,j,h;
  bool EQ;
  pos1= new int[DIM];
  pos2= new int[DIM]; 
  for (i=0;i<N+1;i++) {
    EQ=1;
    get_pos(i,pos1);
    h=table1.hash_function(pos1);
    //cout << pos1[0]<<pos1[1]<<pos1[2]<<"\n"<<h<<"\n"<<pos2[0]<<pos2[1]<<pos2[2]<<"\n";
    while (EQ) {
      table1.get_entry(h,pos2);
      if (pos2[0]==123456789) {
	table1.set_entry(h,pos1);
	EQ=0;
      }
      else {
	for (j=0;j<DIM;j++) {
	  if (pos1[j]!=pos2[j]) EQ=0;
	}
	if (EQ) {
	  table1.clear_table();
	  delete [] pos1;
	  delete [] pos2;
	  return 0;
	}
	else {
	  if (h==table1.get_length()) h=0;
	  else h=h+1;
	  EQ=1;
	}
      }
    }
  }
  table1.clear_table();
  delete [] pos1;
  delete [] pos2;
  return 1;
} 

void Walk::kantor_fun(int * fun) {
  int * dens;
  int * pos;
  int i,j,min,z0,z;
  pos=new int[DIM];
  dens=new int[2*N+1];
  for (i=0;i<2*N+1;i++) {
    dens[i]=0;
  }
  get_pos(0,pos);
  z0=pos[DIM-1];
  min=z0+N;
  for (i=0;i<N+1;i++) {
    get_pos(i,pos);
    z=pos[DIM-1];
    dens[z-z0+N]++;
    if ((z-z0+N)<min) {
      min=z-z0+N;
    }
  }
  for (i=0;i<N+1;i++) {
    fun[i]=dens[i+min];
  }
  delete [] pos;
  delete [] dens;
}
    
    
  
  


  
  

    
  
